rtk 2016

2016.1.1 (preuredi vrstice)

Tipkanje

1. podnaloga

Znašel si se v vlogi zapisnikarja, ki mora na računalniku vnesti seznam n besed. To počneš tako, da s pritiski na tipkovnico vnašaš črko po črko v vnosno polje, ki je na začetku prazno. Ko je v polju izpisana zahtevana beseda, zaključiš vnos s pritiskom na tipko Enter. Beseda pri tem ostane v vnosnem polju. Nato s pritiski na tipko Backspace pobrišeš nekaj (morda vse ali pa nobene) zadnjih črk in nadaljuješ z vnosom naslednje besede.

Naloga

Napisan je program, ki izpiše, najmanj koliko pritiskov tipk boš potreboval, da vneseš podane besede. Vhodne podatke bere s standardnega vhoda.

Vrstice programa so se premešale. Uredi jih, da bo program pravilno deloval.

stevilo_besed = int(input())
prejsnja_beseda, beseda = '', ''
vnosi = 0
    beseda = input()
    dolzina_besede = len(beseda)
    vnosi += backspace + novi_vnosi + 1  # 1 za Enter
    dolzina_prejsnje = len(prejsnja_beseda)
    # Pogledamo, v koliko znakih se za beseda ujema s prejšnjo
    ujemanje = 0
for i in range(stevilo_besed):
    while (ujemanje < min(dolzina_prejsnje, dolzina_besede)) and (prejsnja_beseda[ujemanje] == beseda[ujemanje]):
    backspace = dolzina_prejsnje - ujemanje
        ujemanje += 1
    novi_vnosi = dolzina_besede - ujemanje
    prejsnja_beseda = beseda
print(vnosi)

Vhodni podatki

V prvi vrstici je število besed, nato pa sledi ustrezno število vrstic, v vsaki od njih je po ena beseda. Predpostaviš lahko, da besede vsebujejo le male črke angleške abecede, vendar to ni ključnega pomena. Posamezna beseda je dolga največ $100$ znakov.

Izhodni podatki

Izpis števila potrebnih pritiskov tipk, da vnesemo podane besede.

Primer

Primer vhoda:

>>> 3
>>> abc
>>> aaaa
>>> ba

Pripadajoči izhod:

17

Uradna rešitev

stevilo_besed = int(input())
prejsnja_beseda, beseda = '', ''
vnosi = 0
for i in range(stevilo_besed):
    beseda = input()
    dolzina_besede = len(beseda)
    dolzina_prejsnje = len(prejsnja_beseda)
    # Pogledamo, v koliko znakih se za beseda ujema s prejšnjo
    ujemanje = 0
    while (
                ujemanje < min(dolzina_prejsnje, dolzina_besede)
    ) and (
                prejsnja_beseda[ujemanje] == beseda[ujemanje]):
        ujemanje += 1
    backspace = dolzina_prejsnje - ujemanje
    novi_vnosi = dolzina_besede - ujemanje
    vnosi += backspace + novi_vnosi + 1  # 1 za Enter
    prejsnja_beseda = beseda
print(vnosi)

2016.1.2 (preuredi vrstice)

Zoom

1. podnaloga

Na računalniku gledamo zemljevid, ki pokriva v koordinatnem sistemu območje $[x_1, x_2] × [y_1, y_2]$. Razdelimo ga na štiri četrtine in jih označimo: $0$ je zgornja leva, $1$ je zgornja desna, $2$ je spodnja leva in $3$ je spodnja desna. Izberemo si eno od četrtin in približamo prikaz zemljevida tako, da vidimo le še to četrtino. Tudi njo razdelimo na četrtine in približamo v eno od njih. Ta korak še nekajkrat ponovimo. Z nizom, ki ga sestavljajo znaki 0, 1, 2 in 3, lahko opišemo, v katero četrtino smo se premaknili na vsakem koraku.

Primer za niz "120" in zemljevid $[0, 1] × [0, 1]$:

Začnemo z območjem v obliki pravokotnika, ki ga določata točki $(0, 0)$ in $(1, 1)$. Razdelimo ga na četrtine in približamo v četrtino, označeno z $1$, kot pravi niz.

Sedaj je naše območje pravokotnik, določen s točkama $(0.5, 0.5)$ in $(1, 1)$. Zopet območje razdelimo na četrtine in tokrat približamo na četrtino, označeno z $2$.

Sedaj je naše območje pravokotnik, določen s točkama $(0.5, 0.5)$ in $(0.75, 0.75)$. Zopet območje razdelimo na četrtine in približamo na četrtino, označeno z $0$.

Upoštevali smo celoten niz in približali do območja v obliki pravokotnika, določenega s koordinatami $(0.5, 0.625)$ in $(0.625, 0.75)$.

Naloga

Napisana je funkcija zoom(s, x1, x2, y1, y2), ki za dani niz s (zaporedje znakov 0, 1, 2, 3, ki opisujejo potek približevanja) in koordinate $x_1$, $x_2$, $y_1$, $y_2$ celotnega zemljevida (pri tem zagotovo velja $x_1 < x_2$ in $y_1 < y_2$) vrne koordinate tistega območja, ki ga gledamo po zadnjem koraku približevanja. Vrstice naše funkcije so se premešale. Uredi jih, da bo funkcija zopet delovala.

def zoom(s, x1, y1, x2, y2):
    for znak in s:
        if znak == '0' or znak == '2':
            y1 = y
        else:
            x2 = x
        if znak == '0' or znak == '1':
            y2 = y
        else:
            x1 = x
        y = (y1 + y2) / 2
        x = (x1 + x2) / 2
    return x1, y1, x2, y2

Vhodni podatki

Niz, sestavljen iz nizov '0', '1', '2', '3' ter koordinate območja tipa float.

zoom(s, x1, y1, x2, y2)

Izhodni podatki

Koordinate območja tipa float, ki ga gledamo po zadnjem koraku približevanja.

Primer

>>> zoom('120', 0., 0., 1., 1.)
(0.5, 0.625, 0.625, 0.75)

Uradna rešitev

def zoom(s, x1, y1, x2, y2):
    """Za dani niz s, ki opisuje potek približevanja, in koordinate celotnega
    zemljevida x1, y1, x2, y2 izračuna in vrne koordinate tistega območja,
    ki ga gledamo po zadnjem koraku približevanja."""
    for znak in s:
        x = (x1 + x2) / 2
        y = (y1 + y2) / 2
        if znak == '0' or znak == '1':
            y1 = y
        else:
            y2 = y
        if znak == '0' or znak == '2':
            x2 = x
        else:
            x1 = x
    return x1, y1, x2, y2

2016.1.3 (preuredi vrstice)

Zaklepajski izrazi

1. podnaloga

Oklepajski izrazi so nizi, ki jih sestavljajo sami oklepaji in zaklepaji, morajo pa biti pravilno gnezdeni. Oklepaji in zaklepaji so lahko različnih oblik:

• okrogli ( ),
• oglati [ ],
• zaviti { },
• kotni < >.

Pravilno gnezdeni pomeni, da mora imeti vsak oklepaj tudi pripadajoč zaklepaj enake oblike (in obratno), podniz med njima pa mora biti tudi sam zase oklepajski izraz.

Primeri oklepajskih izrazov: <<>>, ()<>(), {[{}()]<>}.

Primeri nizov, ki niso oklepajski izrazi: (()(, ([)], <>><<>.

Naloga

Dan je nek niz s, v katerem se pojavljajo le zaklepaji različnih oblik - ) ] } > - in zvezdice $\ast$.

Napisali smo funkcijo dopolni(s), ki vsako zvezdico v nizu s spremeni v enega od oklepajev - torej znakov ( [ { < - tako, da iz tega na koncu nastane pravilno gnezden oklepajski izraz. Vrstice so premešane. Uredi jih, da bo program zopet deloval.

def dopolni(s):
    """Če je mogoče, vrne popravljen niz, da predstavlja oklepajski izraz.
    Če ni mogoče, vrne niz 'Problem je nerešljiv.'."""

    # Niz beremo od konca proti začetku
    n = len(s)

    # V pythonu nizu ne moremo kar spremeniti znaka. Zato si niz napišemo v seznam.
    izraz = list(s)

    sklad = ''
            sklad += s[i]
    velikost_sklada = len(sklad)
    for i in range(n-1, -1, -1):
            velikost_sklada += 1
        if s[i] != '*':
        # sicer imamo zvezdico
        else:
            # Pobrišemo zaklepaj z vrha sklada in spremenimo trenutno zvezdico v pripadajoči oklepaj.
            if velikost_sklada == 0:
                return "Problem je nerešljiv."
            zaklepaj = sklad[-1]
            sklad = sklad[0:velikost_sklada - 1:]
            velikost_sklada -= 1
            if zaklepaj == ')':
                izraz[i] = '<'
            elif zaklepaj == ']':
                izraz[i] = '('
            elif zaklepaj == '}':
                izraz[i] = '['
            elif zaklepaj == '>':
                izraz[i] = '{'
    if velikost_sklada == 0:
        return "Problem je nerešljiv."
    else:
        return ''.join(izraz)

Vhodni podatki

Niz, v katerem se pojavljajo le zaklepaji različnih oblik in zvezdice.

Izhodni podatki

Funkcija naj vrne popravljeni niz. Če se izkaže, da niza ni mogoče ustrezno popraviti, da bi nastal oklepajski izraz, naj vrne niz "Problem je nerešljiv."

Primer

Iz "$\ast\ast$]$\ast$))" lahko naredimo "( [ ] ( ) )".

Iz "$\ast\ast\ast\ast$>$\ast$)" pa ne moremo narediti veljavnega oklepajskega izraza, ne glede na to, kako spreminjamo zvezdice v oklepaje.

Uradna rešitev

def dopolni(s):
    """Če je mogoče, vrne popravljen niz, da predstavlja oklepajski izraz.
    Če ni mogoče, vrne niz 'Problem je nerešljiv.'."""

    # Niz beremo od konca proti začetku
    n = len(s)

    # V pythonu nizu ne moremo kar spremeniti znaka. Zato si niz napišemo v seznam.
    izraz = list(s)

    sklad = ''
    velikost_sklada = len(sklad)
    for i in range(n-1, -1, -1):
        if s[i] != '*':
            sklad += s[i]
            velikost_sklada += 1
        # sicer imamo zvezdico
        else:
            # Pobrišemo zaklepaj z vrha sklada in spremenimo trenutno zvezdico v pripadajoči oklepaj.
            if velikost_sklada == 0:
                return "Problem je nerešljiv."
            zaklepaj = sklad[-1]
            sklad = sklad[0:velikost_sklada - 1:]
            velikost_sklada -= 1
            if zaklepaj == ')':
                izraz[i] = '('
            elif zaklepaj == ']':
                izraz[i] = '['
            elif zaklepaj == '}':
                izraz[i] = '{'
            elif zaklepaj == '>':
                izraz[i] = '<'
    if velikost_sklada == 0:
        return ''.join(izraz)
    else:
        return "Problem je nerešljiv."

2016.1.4 (preuredi vrstice)

Izštevanka

1. podnaloga

Otroci so se že malo naveličali vsakokrat uporabljati preprosto izštevanko "An ban pet podgan" za določitev tistega, ki lovi, zato so se odločili za manjšo spremembo: vsak naj ima dve življenji, kdor ostane brez, je "izbrani".

V krog se postavi $n$ otrok, vsak stoji z obema nogama na tleh (t.j. ima dve življenji). Naj bodo oštevilčeni z zaporednimi številkami od $1$ do $n$. Začnemo pri otroku številka $1$ in od njega naredimo $k$ korakov po krogu (pri tem torej njega ne štejemo, ampak štejemo šele otroke od $2$ naprej) - $k$ je pozitivno celo število, lahko je tudi večje od $n$. Otrok na tako določenem mestu mora dvigniti nogo (izgubi življenje). Če mora dvigniti še drugo in zato pasti, je izštevanke konec in ta otrok postane "izbrani". Če pa še vedno stoji na eni nogi (je pravkar izgubil šele prvo življenje), se izštevanka nadaljuje (spet začne šteti) pri otroku neposredno za njim, hkrati pa izštevanko podaljšamo za eno besedo, torej $k$ povečamo za $1$.

Naloga

Napisan je program, ki prebere dve pozitivni celi števili - $n$ in začetno vrednost $k$, opravi korake izštevanke in izpiše številko "izbranega" otroka, to je tistega, ki je padel po tleh, ker je izgubil obe življenji. Število otrok $n$ je vsaj $1$ in kvečjemu $100$.

Vrstice so se premešale in zamaknile. Uredi jih, da bo program zopet deloval.

k = int(input())
n = int(input())
zivljenja = []
zivljenja.append(2)
k += 1
for i in range(n):
i = 0
zivljenja[i] -= 1
i = (i + k) % n
while zivljenja[i] > 0:
print(i+1)

Vhodni podatki

Dve pozitivni celi števili, prvo predstavlja število otrok, drugo pa dolžino izštevanke.

Izhodni podatki

Program izpiše število "izbranega" otroka.

Primer

Če imamo $n = 5$ in $k = 3$, morajo po vrsti dvigovati noge otroci $4$, $3$, $3$ in igre je konec - izbran je otrok številka $3$.

>>> 5
>>> 3
3

Uradna rešitev

n = int(input())
k = int(input())
zivljenja = []
for i in range(n):
    zivljenja.append(2)
i = 0
while zivljenja[i] > 0:
    i = (i + k) % n
    zivljenja[i] -= 1
    k += 1
print(i+1)

2016.1.5 (preuredi vrstice)

H-indeks

1. podnaloga

Hirschev indeks (krajše tudi h-indeks) je ena izmed številnih ocen, ki poskušajo meriti uspešnost raziskovalcev.

Cilj ocene h-indeks je uravnotežiti produktivnost (število objavljenih člankov) in vplivnost (citiranost njegovih člankov) posameznega raziskovalca. H-indeks je definiran kot največje celo število $h$, za katerega velja, da je raziskovalec objavil $h$ člankov, kjer je bil vsak izmed teh člankov citiran vsaj $h$-krat.

Naloga

Napisana je funkcija h_indeks(clanki), ki iz podanega seznama citiranosti člankov izračuna h-indeks. Vrstice so se premešale. Uredi jih, da bo funkcija zopet delovala.

def h_indeks(clanki):
    st_clankov = len(clanki)
    for clanek in clanki:
    stevec = [0] * st_clankov
    return h
            stevec[clanek] += 1
            stevec[st_clankov - 1] += 1
        else:
    """Izračuna h-indeks iz danega seznama citiranosti člankov."""
    s = 0
    h = st_clankov
    if 1 <= h <= stevec[h-1]:
        h -= 1
        s += stevec[h]
    while h > s:
        if clanek >= st_clankov:
        return h

Vhodni podatki

Dani seznam je sestavljen iz števil, ki za posamezne članke povedo, kolikokrat so bili citirani.

Izhodni podatki

Funkcija vrne h-indeks za podani seznam.

Primer

Če imamo seznam [6, 5, 3, 2, 5, 10, 5, 7], je njegov h-indeks enak $5$, kajti v seznamu obstaja vsaj pet elementov, večjih ali enakih $5$, ne obstaja pa v njem vsaj šest elementov, večjih ali enakih $6$.

Uradna rešitev

def h_indeks(clanki):
    """Izračuna h-indeks iz danega seznama citiranosti člankov."""
    st_clankov = len(clanki)
    stevec = [0] * st_clankov
    for clanek in clanki:
        if clanek >= st_clankov:
            stevec[st_clankov - 1] += 1
        else:
            stevec[clanek] += 1
    s = 0
    h = st_clankov
    if 1 <= h <= stevec[h-1]:
        return h
    while h > s:
        h -= 1
        s += stevec[h]
    return h